The present application relates to a motion-vector searching method for searching for a motion vector indicating a movement to an observed image of an input picture from a reference image included in the input picture as an image separated away along the time axis from the observed image by a small time difference by execution of the steps of dividing the observed image into a plurality of observed blocks, dividing the reference image into a plurality of reference blocks and comparing the reference blocks with a selected one of the observed blocks, as well as relates to a motion-vector searching apparatus adopting the motion-vector searching method.
In general, the processing to compress a moving picture includes a process to detect a motion vector indicating a movement from a reference frame to an observed frame separated away from the reference frame along the time axis by a small time difference and make use of the motion vector to carry out a motion compensation prediction coding operation. In this specification, a motion vector is also referred to as an optimum position vector. The process to detect a motion vector of a moving picture is also applied to processing to compensate an image for an effect of hand trembling experienced by a digital camera. The process to detect a motion vector may adopt one of a variety of available methods including a generally known block matching method. In accordance with the block matching method, a motion vector indicating a movement to an observed image of an input picture from a reference image included in the input picture as an image separated away along the time axis from the observed image by a small time difference is detected by execution of the steps of dividing the observed image into a plurality of observed blocks, dividing the reference image into a plurality of reference blocks and comparing the reference blocks in a search area with a selected one of the observed blocks in order to search the search area for a reference block most similar to the selected observed block. To put it in detail, the selected observed block is compared with each of a plurality of aforementioned reference blocks in the search area in order to find evaluation values each representing the degree of similarity and determine the highest degree of similarity.
Such a process to detect a motion vector is known as processing having a very large amount of computation. By the way, the process to detect a motion vector is referred to as a process to search for a movement, a process to estimate a movement, a process to infer a movement or a process to calculate a movement to mention a few. On the other hand, processing to process a moving picture having a high frame rate to result in a picture with a good quality is also required. For this reason, increasing the processing speed of a process to search for a motion vector becomes an important technological theme. The processing speed of a process to search for a motion vector can be increased by reducing the amount of processing and/or implementing parallel processing.
In addition, reducing the power consumption of a device for carrying out the process to search for a motion vector also becomes an important technological theme as well. As already generally known, the power consumption of the device can be reduced most effectively by decreasing the operating frequency of the device. For this reason, by the same token, reduction of the amount of processing and/or implementation of parallel processing are indispensable to efforts to reduce the power consumption.
By the way, in order to increase the processing speed of the process to search for a motion vector, a variety of speed-increasing methods have been proposed. The proposed speed-increasing methods include search-type methods represented by a diamond search technique disclosed in non-patent document 1 listed below. By adoption of the diamond search method, it is possible to increase the processing speed of the process to search for a motion vector while sustaining a high picture quality. In accordance with the diamond search method, first of all, a vector existing on a position-vector plane is determined. Then, an area surrounding the vector is taken as the first search area. Subsequently, vectors in the first search area are compared with each other in order to determine an optimum vector oriented in a direction in which a next search area including vectors with smaller values is separated away from the first search area. Then, the next search area is set as the second search area. These operations are carried out repeatedly till eventually the evaluation value becomes a minimum at the center of the set search area or the boundary of the entire search area (or the entire picture) is undesirably exceeded. By adopting this method, the number of vectors to be searched for a full search process can be reduced substantially. In this method, however, a technique to further increase the processing speed of the process to search for a motion vector corresponding to the minimum evaluation value is not taken into account.
In addition, parallel processing is absolutely required in the effort to increase the processing speed of the process to search for a motion vector. A technology for loading data from a memory with a high degree of efficiency is of importance to implementation of the parallel processing. An architecture for loading data from a memory with a high degree of efficiency has been proposed as described in documents such as patent document 1 listed below. By adoption of a method based on this proposed technology, it is possible to carry out processes to compute evaluation values of vectors as parallel processing. By the way, patent document 1 does not describe a method for further increasing the processing speed of the process to search for a motion vector. In order to further increase the processing speed of the process to search for a motion vector, it is necessary to convert computation for each vector into a parallel process and to carry out the computation processes for all vectors concurrently.    Non-patent Document 1: S. Zhu and K. Ma, “A New Diamond Search Algorithm for Fast Block Matching Motion Estimation,” International Conference on Information, Communications and Signal Processing ICICS '97 Singapore, 9-12 Sep. 1997.    Patent Document 1: Japanese Patent Laid-open No. 2005-530420.